package code.classic150on2025;

import java.util.*;

public class SingleDP {
    // 53. 最大子数组和
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    // 918. 环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        // 计算环形子数组，直接算不好算
        // 在左右两边都有的情况下，转为计算中间的最小和
        // 这样，同时计算子数组的最大和和最小和，最小和就是穿越环形的最大和的情况
        int len = nums.length;
        int sum = Arrays.stream(nums).sum();
        int[] dp_max = new int[len];
        int[] dp_min = new int[len];
        dp_max[0] = nums[0];
        dp_min[0] = nums[0];
        for (int i = 1; i < len; i++) {
            dp_max[i] = Math.max(nums[i], dp_max[i - 1] + nums[i]);
            dp_min[i] = Math.min(nums[i], dp_min[i - 1] + nums[i]);
        }
        // 注意 在计算dp_min的时候不能选所有的元素
        int dpMin = Arrays.stream(dp_min).min().getAsInt();
        int dpMax = Arrays.stream(dp_max).max().getAsInt();
        if (dpMin == sum)
            return dpMax;
        return Math.max(dpMax, sum - dpMin);
    }

    // 198. 打家劫舍
    public int rob(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1]; // dp[i]表示前i个房屋获得的最大利益
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[len];
    }

    // 139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        // 可重复选、顺序无关 ➡️ 爬楼梯、一维dp
        int len = s.length();
        // dp[i] 表示能不能构成s的前i个
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (String word : wordDict) {
                // 如果 word 长度大于当前的 i，说明不合适
                if (word.length() > i)
                    continue;
                // 如果 word 不能和当前匹配，不合适
                if (!s.substring(i - word.length(),i).equals(word))
                    continue;
                dp[i] = dp[i] || dp[i - word.length()];
            }
        }
        return dp[len];
    }

    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // 可重复选+顺序无关=爬楼梯一维dp
        int len = coins.length;
        int[] dp = new int[amount + 1]; // dp[i] 表示凑成 i 金额需要的最少硬币个数
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (coin > i)
                    continue;
                if (dp[i - coin] == Integer.MAX_VALUE)
                    continue;
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    // 300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // 一种“新颖”的方法：设定dp[i]表示长度为i的递增子序列的末尾元素，这个元素越小越好
        int len = nums.length;
        int[] dp = new int[len];
        int maxNum = 0;
        for (int num : nums) {
            // 找这个num的插入位置
            int left = 0, right = maxNum;
            int insertPos = maxNum;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (num <= dp[mid]) {
                    insertPos = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            dp[insertPos] = num;
            if (insertPos == maxNum)
                maxNum++;
        }
        return maxNum;
    }
}
